/**
 * ‘上浮’ 调整
 * @param array 待调整的堆
 * 
 */

 function upAdjust(array){
     let childIndex = array.length -1;
     let parentIndex = (childIndex -1)/2;
     //temp保存插入的叶子节点值 用于最后赋值
     let temp = array[childIndex];
     while(childIndex >0 && temp <array[parentIndex]){
         //无需真正交换 单项赋值即可
         array[childIndex] = array[parentIndex];
         childIndex = parentIndex;
         parentIndex = (parentIndex - 1) /2;
     }
     array[childIndex] = temp;
 }

 /**
  * '下沉' 调整 
  * @param array 待调整的堆
  * @param parentIndex 要下沉的父节点
  * @param length 堆的有效大小
  */

  function downAdjust(array,parentIndex,length){
      //temp 保存父节点值 用于最后的赋值
      let temp = array[parentIndex];
      let childIndex = 2 * parentIndex +1;
      while(childIndex < length){
          //如果有 右孩子 且右孩子小于左孩子的值 则定位到右孩子
          if(childIndex +1 <length && array[childIndex +1] <array[childIndex]){
              childIndex ++;
          }
          //如果 父节点 小于任何一个孩子的值 则直接跳出
          if(temp <= array[childIndex]){
              break;
          }
          //无需真正交换 单向赋值即可
          array[parentIndex] = array[childIndex];
          parentIndex = childIndex;
          childIndex = 2 * childIndex +1;
      }
      array[parentIndex] = temp;
  }

  /**
   * 构建堆
   * @param array 待调整的堆
   */

   function buildHeap(array){
       //从最后一个非叶子节点开始 依次做 下沉调整
       for(let i = (array.length -2)/2;i>=0;i--){
           downAdjust(array,i,array.length);
       }
   }

   function main(args){
       let arr =[1,3,2,6,5,7,8,9,10,0]
       upAdjust(arr);
       console.log(arr,'a')
       let arr2 = [7,1,3,10,5,2,8,9,6];
       buildHeap(arr2)
       
   }
   main();